\documentclass[11pt,a4paper,oneside]{report}

\usepackage{DocumentStyle}
\usepackage[dutch]{babel} 
\selectlanguage{dutch} 


\begin{document}
\title{Ori\"entatie Algoritmen}

\author{
	Daniel van Cleef\\
	Ron Talman\\	
	Geert Weening\\
	Leander Nijland	\\
	Ingmar Raa\\
	Mark Rietveld\\
	(eii7aab)\\\\
	University of Applied Sciences,\\
	Enschede,\\
	The Netherlands\\
}
\date{\today}
\maketitle

\tableofcontents

\chapter{Inleiding} % (fold)
\label{cha:inleiding}
Ter voorbereiding op het project binnen de minor Advanced Algorithms is het zaak basiskennis op te doen op het gebied van algoritmiek. In dit verslag staan de resultaten van deze leerweg. In Hoofdstuk~\ref{cha:standaaralgoritmen} staan de bevindingen over onderzoek naar sorteeralgoritmen en graafalgoritmen. Vervolgens wordt in Hoofdstuk~\ref{cha:Project_gerelateerde_algoritmen} dieper in gegaan op de algoritmes die meer betrekking hebben op ons gekozen project, namelijk het bin-packing probleem\footnote[1]{Zie PvA voor gedetailleerde projectomschrijving.}. In Hoofdstuk~\ref{cha:datastructuur} wordt de datastructuur van de omgeving waarin de verschillende algoritmes zijn ge\"implementeerd omschreven. Hoofdstuk~\ref{cha:analyse} bevat een analyse van de ge\"implementeerde algoritmes. Hierin wordt beschreven hoe we de verschillende algoritmes hebben getest. Ook bevat dit hoofdstuk de resultaten van deze analyse. 
% chapter inleiding (end)

\chapter{Standaaralgoritmen} % (fold)
\label{cha:standaaralgoritmen}

\section{Sorteer Algoritmen} % (fold)
\label{sec:sorteer_algoritmen}

\subsection{Insertion Sort} % (fold)
\label{sub:insertion_sort}
Insertion sort is een simpel sorterings algoritme dat voordelig is bij kleine sets data. Bij kleine sets data is de tijd meestal geen groot probleem en dit algoritme verdient dan de voorkeur omdat het vrij simpel is. Met grote sets data is insertion sort geen voordeldig algoritme omdat de uitvoertijd dan te groot wordt.

\subsubsection{Werking} % (fold)
\label{ssub:werking_Insertion Sort}
Een lijst wordt gesorteerd door het tweede element te pakken en te vergelijken met het eerste element. Als dit element kleiner is, dan wordt deze vooraan gezet en als dit element groter is kan deze blijven staan. Voor elke volgende stap weet je dus dat de elementen tot dan toe zijn gesorteerd. Voor het herpositioneren van het element waar je dan bent worden alle elementen die groter zijn naar rechts verschoven.
% subsubsection werking (end)

\subsubsection{Voorbeeld} % (fold)
\label{ssub:voorbeeld_insertion_sort}
Lijst lst [3, 7, 6, 4]
\begin{enumerate}
	\item Het tweede element, 7, wordt vergeleken met het eerste element, 3. Het tweede element, 7, is groter en kan blijven staan.
	
	\emph{Resultaat:} 	[3, 7, 6, 4]
	\item Het derde element, 6, wordt vergeleken met de voorgaande elementen en alle elementen groter dan 6 worden naar rechts verschoven. 
	
	\emph{Resultaat:} [3, 6, 7, 4]
	\item Het vierde, en laatste, element, 4, wordt vergeleken met de voorgaande elementen alle elementen groter dan 4 worden naar rechts verschoven
	
	\emph{Resultaat:} [3, 4, 6, 7]
\end{enumerate}

% subsubsection voorbeeld (end)

\subsubsection{Pseudo-code} % (fold)
\label{ssub:pseudo_code_insertion_sort}
\begin{lstlisting}[label=inseriton_sort_pseudocode, caption=Insertion sort pseudo-code]
for( int positie = 1; positie < lijst.length; p++ ) {
	temp = lijst[ positie ];	// huidig element opslaan
	int j = positie;
	// Elk element dat groter is dan het huidig element wordt naar rechts verplaatst
	for(; j > 0 && temp < lijst[ j-1 ]; j-- ) {
		lijst[ j ] = lijst[ j - 1];
	}
	// En op de overgebleven plek komt het element dat we aan het verplaatsten waren
	lijst[ j ] = temp;
}
\end{lstlisting}
% subsubsection pseudo_code (end)

% subsection insertion_sort (end)	

\subsection{Quick Sort} % (fold)
\label{sub:quick_sort}
Quicksort is een “divide-and-conquer” algoritme. De totale set wordt in in tweeen gesplitst (divide), deze beide delen worden gesorteerd (conquer) en vervolgens weer samengevoegd. De verdeling wordt gekozen door een zogenaamd “pivot” punt. Er wordt een punt in de lijst gekozen, vaak het midden, en alle elementen in de lijst die kleiner zijn dan het pivot punt komen in de ene lijst en alle elementen die groter zijn in de andere lijst. 

\subsubsection{Werking} % (fold)
\label{ssub:werking_quick_sort}
Quicksort werkt door bovenstaand principe recursief toe te passen. Voor elke helft wordt weer een pivot punt gekozen en een lijst met groter en kleiner dan het pivot punt opgebouwd. Dit gaat door tot een lijst nog 1 of geen elementen meer bevat.
% subsubsection werking (end)

\subsubsection{Voorbeeld} % (fold)
\label{ssub:voorbeeld_quick_sort}
Lijst lst [12, 3, 5, 9, 11]
\begin{enumerate}
\item Kies een pivot, we nemen 5. Vervolgens wordt de lijst verdeeld in groter en kleiner dan 5 lijsten. 
\emph{Resultaat:} [3], de pivot 5 en [12, 9, 11]
\item De kleiner dan lijst heeft nog een grotte van 1 en wordt niet verder gesorteerd. Voor de groter dan lijst kiezen we 9 en verdelen de elementen.
\emph{Resultaat:} [], de pivot 9 en [12, 11]
\item Kleiner dan lijst van 9 heeft geen elementen meer en wordt niet verder gesorteerd. Voor de groter dan lijst kiezen we 12 als pivot en verdelen de elementen.
\emph{Resultaat:} [11], de pivot 12 en []
\item Lijsten uit de stappen samenvoegen: 
\begin{itemize}
\item $[11]$, de pivot 12 en $[] \rightarrow [11,12]$
\item $[]$, de pivot 9 en $[11,12] \rightarrow [9, 11, 12]$
\item $[3]$, de pivot 5 en $[9, 11, 12] \rightarrow [3, 5, 9, 11, 12]$
\end{itemize}
\end{enumerate}

% subsubsection voorbeeld (end)

% subsection quick_sort (end)

\subsection{Merge Sort} % (fold)
\label{sub:merge_sort}

Het merge sort algoritme is in 1945 bedacht door John von Neumann. Het merge sort algoritme behoort tot de oudste algoritmen bedacht voor computerprogramma’s. Merge sort kan gebruikt worden voor het ordenen van een lijst van elementen van klein naar groot. 

Het basisprincipe van het algoritme is dat een groot probleem wordt opgedeeld in kleinere problemen, die gemakkelijker zijn op te lossen. In dit geval wordt een lijst in twee\"en gedeeld

\subsubsection{Werking} % (fold)
\label{ssub:werking_merge_sort}
Eerst wordt er gecontroleerd of de lengte van de lijst 0 of 1 is. In die situatie is de lijst al gesorteerd en geeft merge sort zijn resultaat terug. De volgende stappen worden uitgevoerd als dit niet het geval is
\begin{enumerate}
	\item De lijst wordt in twee ongeordende lijsten, van dezelfde grootte opgebroken.
	\item De vorige stap wordt herhaald totdat er afzonderlijke elementen overblijven.(recursie).
	\item De lijst wordt per paren van 2 weer bij elkaar gevoegd tot een hele lijst. Bij elke samenvoeging wordt een deellijst gesorteerd. Dit resulteert dus uiteindelijk in een volledig gesorteerde lijst.
\end{enumerate}
Figuur~\ref{fig:mergesort} illustreert de bovengenoemde stappen

\begin{figure}[htb]
\begin{center}
\includegraphics[width=0.7\textwidth]{./images/mergesort}
\caption{}
\label{fig:mergesort}
\end{center}
\end{figure}

% subsubsection werking (end)
% subsection merge_sort (end)

\subsection{Bubble Sort} % (fold)
\label{sub:bubble_sort}
Bubble Sort is een sorteeralgoritme. Het dankt de naam aan het feit dat op deze manier de te sorteren elementen in een gegeven rij \'e\'en voor \'e\'en op de juiste volgorde worden gezet. Ze "Bubblen" naar boven bij wijze van spreken.

\subsubsection{Werking} % (fold)
\label{ssub:werking_bubble_sort}
Stel we willen een reeks met n getallen op volgorde van klein naar groot hebben, dan werkt Bubble Sort als volgt

\begin{itemize}
	\item Er wordt ge\"itereerd over de te sorteren rij en ieder element wordt met het volgende element vergeleken. In ons geval wil dit zeggen: Wanneer element $x + 1$ groter is dan element $x$, verwissel ze van lokatie binnen de rij ( $x$ komt dan op lokatie $x + 1$ en vice versa ).
	\item Itereer opnieuw over de rij, tot aan het \'e\'en na laatste element $( n - 1 )$. Immers is deze nu het grootste element in de rij.
	\item Itereer opnieuw over de rij, dit keer tot het twee na laatste element $( n - 2 )$. Immers zijn de laatste twee elementen nu de grootste twee in de rij.
	\item Herhaal het itereren over de rij, tot aan het eerste element $( n - ( n - 1 ) )$ oftewel element 1.
\end{itemize}
% subsubsection werking (end)

\subsubsection{Voorbeeld} % (fold)
\label{ssub:voorbeeld_bubble_sort}

We hebben een reeks getallen: [ 4, 8, 1, 9, 7 ]. We willen deze getallen sorteren van klein naar groot, dan gaat het algoritme als volgt:
\begin{itemize}
	\item Binnen de rij worden de eerste twee getallen vergeleken ( 4 en 8 ). Aangezien 8 groter is dan 4 wordt er niet van plek gewisseld.
	\item Vervolgens wordt er gekeken naar het tweede en derde getal ( 8 en 1 ). Hier is 1 niet groter dan 8 en worden deze wel van plek gewisseld. De rij is nu: [ 4, 1, 8, 9, 7 ].
	\item Het derde en vierde getal zijn nu aan de beurt ( nu 8 en 9 ). Aangezien 9 groter is dan 8, blijven de plekken wederom gelijk.
	\item Als laatste van deze iteratie zijn het vierde en vijfde getal aan de beurt ( namelijk 9 en 7 ). Aangezien 9 groter is dan 7 worden ze wel van plek gewisseld. De rij is nu: [ 4, 1, 8, 7, 9 ].
\end{itemize}
Dit proces herhaalt zich, alleen stopt het nu bij getal $n - 1$ ( wat in dit geval betekent dat als laatste 8 en 7 vegeleken worden ). De rij is na dit proces: [ 1, 4, 7, 8, 9 ].

Hoewel de rij al op volgorde staat, zal het Bubble Sort algoritme ( de standaard implementatie in ieder geval ) zich blijven herhalen met de stoppunten $n - 2$, $n - 3$ etc. Dit maakt Bubble Sort een niet heel effectief algoritme op grotere rijen getallen.

% subsubsection werking (end)

% subsection bubble_sort (end)

\subsection{Heap Sort} % (fold)
\label{sub:heap_sort}
Heapsort is een sorteeralgortime dat gebruik maakt van een heap om te kunnen sorteren. Een heap is een twee-dimensionale variant van een binaire boom. Dat betekent dat alleen het kleinste element of het grootste element rechtstreeks uit de heap gehaald kan worden. Het ligt eraan of de heap een minHeap is of een maxHeap. Heapsort maakt gebruik van een minHeap.  Hieronder kun je een voorbeeld zien van een minHeap.

\begin{figure}[htb]
\begin{center}
\includegraphics[width=0.7\textwidth]{./images/heapsort}
\caption{}
\label{fig:heapsort}
\end{center}
\end{figure}
Een minHeap wordt meestal  ge\"implementeerd middels een bepaald type datastructuur. Namelijk een priority queue.

\subsubsection{werking} % (fold)
\label{ssub:werking_heap_sort}
\begin{enumerate}
	\item  Als eerst worden alle elementen van de ongesorteerde lijst toegevoegd aan de priority queue. Om het algoritme effici\"enter te maken worden de elementen niet bij iedere toevoeging op de plaats gezet volgens een binaire boom. Deze stap is van orde $O(N)$.  
	\item Wanneer alle elementen in de priority queue zitten, wordt de minHeap pas gevormd. Het vormen van een minHeap is ook van de orde $O(N)$. Dit is een interne sortering dat de elementen op de juiste plaats zet volgens de binaire boom structuur. 
	\item Als laatst wordt telkens het kleinste element uit de minheap gehaald. De elementen die de minHeap verlaten volgen hiermee in oplopende gesorteerde volgorde. Deze stap is van de orde $O(N\log{N})$.
\end{enumerate}

Het heapsort-algortime is in het slechtste geval van de orde $O(N\log{N})$ en is daarmee \'e\'en van de snelste sorteeralgortime.
% subsubsection werking (end)

\subsubsection{Pseudo-code} % (fold)
\label{ssub:pseudo_code_heap_sort}

\begin{lstlisting}[label=pseudo_code_heap_sort, caption=Heap Sort Pseudo-code]
Heapsort(A) {
	BuildHeap(A)
	for i <- length(A) downto 2 {
		exchange A[1] <-> A[i]
		heapsize <- heapsize -1
		Heapify(A, 1)
}

BuildHeap(A) {
	heapsize <- length(A)
	for i <- floor( length/2 ) downto 1
		Heapify(A, i)
}

Heapify(A, i) {
	le <- left(i)
	ri <- right(i)
	if (le<=heapsize) and (A[le]>A[i])
		largest <- le
	else
		largest <- i 
	if (ri<=heapsize) and (A[ri]>A[largest])
		largest <- ri
	if (largest != i) {
		exchange A[i] <-> A[largest]
		Heapify(A, largest)
	}
}
\end{lstlisting}
% subsubsection pseudo_code (end)
% subsection heap_sort (end)
% section sorteer_algoritmen (end)

\section{Graaf Algoritmen} % (fold)
\label{sec:graaf_algoritmen}

\subsection{Shortest Path} % (fold)
\label{sub:shortest_path}
Er zijn verschillende soorten kortste pad algoritmen, maar allen hebben het doel: Vind een pad tussen twee knopen waarvan het totale gewicht van de belopen zijdes zo laag mogelijk is.

Een korste pad algoritme kan verschillende vormen aannemen:
\begin{itemize}
	\item Een \emph{enkel bronnig kortste pad} wordt gebruikt om vanaf \'e\'en bron knoop het kortste pad te vinden naar alle andere knopen in de graaf.
	\item Een \emph{enkel doelig korste pad} wordt gebruikt om vanaf alle vertices een kortste pad te vinden naar \'e\'e doel knoop in de graaf.
	\item Een \emph{alle paren korste pad} wordt gebruikt om het korste pad te vinden tussen ieder paar knopen binnen een graaf.
\end{itemize}

\subsubsection{Voorbeelden} % (fold)
\label{ssub:voorbeelden}
Voorbeelden van enkel bronnig korste pad algoritmen zijn:
\begin{itemize}
	\item Het algoritme van Dijkstra zie paragraaf~\ref{sub:dijkstra}. (De graaf mag geen negatieve getallen bevatten.)
	\item Het algoritme van Bellman-Ford zie paragraaf~\ref{sub:belman_ford}. (Deze mag wel negatieve getallen bevatten.)
\end{itemize}
Voorbeeld van een enkel doelig kortste pad algoritme:
\begin{itemize}
	\item Het algoritme van Dijkstra zie paragraaf~\ref{sub:dijkstra}. (De graaf mag geen negatieve getallen bevatten.)
\end{itemize}
Voorbeelden van alle paren kortste paden algoritmen zijn:
\begin{itemize}
	\item Het algoritme van Floyd-Warshall zie paragraaf~\ref{sub:floyd_warshall}..
	\item Het algoritme van Johnson zie paragraaf~\ref{sub:johnsons}.
\end{itemize}

% subsubsection voorbeelden (end)
% subsection shortest_path (end)

\subsection{Dijkstra} % (fold)
\label{sub:dijkstra}
Dijkstra's algoritme is een effici\"ente manier voor het vinden van de goedkoopste routes van een start vertex naar alle andere vertices in een gewogen graaf. De graaf mag alleen edges met gewichten groter dan 0 bevatten, anders kan het algoritme in een oneindige loop terecht komen.

\subsubsection{Voorbeeld} % (fold)
\label{ssub:voorbeeld_dijkstra_algoritme}

\begin{figure}[htb]
\begin{center}
\includegraphics[width=0.4\textwidth]{./images/dijkstra}
\caption{}
\label{fig:dijkstra}
\end{center}
\end{figure}
In Figuur~\ref{fig:dijkstra} beginnen in punt 1 en willen de kortste afstand en route tot elk ander punt weten. We kijken eerst naar alle directe buren van punt 1. het punt met de korste afstand tot 1 is punt 2, met afstand 7. We markeren bij punt 2 dat de kortste afstand 7 is, en dat het vorige punt punt 1 is. Nu we dit gemarkeerd hebben hoeven we voor dit punt nooit meer te bepalen wat de afstand is, we hebben de minimale afstand al gevonden.

We kijken nu naar de directe buren van alle punten die we al gehad hebben. Dit zijn punt 3, punt 4 en punt 6. Het dichtste bij het startpunt is nu punt 3. We markeren in punt 3 dat de afstand 9 is, en dat het voorgaande punt nummer 1 is.

We gaan verder met alle nieuwe buren, punt 4 en punt 6. Punt 4 ligt op afstand $20 (9 + 11)$ en punt 6 ligt op afstand $11 (9 + 2)$. We markeren in punt 6 dat de afstand 11 is en dat het vorige punt 3 is.

We hebben nu nog twee buren over, beide liggen op dezelfde afstand van het startpunt. Het maakt nu niet uit welk punt we eerst kiezen. We markeren in punt 4 dat de afstand 20 is en dat het vorige punt 3 is. Daarna markeren we in punt 5 dat de afstand tot het startpunt 20 is, en dat het voorgaande punt nummer 6 is.
% subsubsection voorbeeld (end)

\subsubsection{Resultaat} % (fold)
\label{ssub:resultaat_dijkstra_algoritme}
We kunnen nu van elk punt de kortste afstand aflezen en de kortste route terugvinden. Als we de kortste route voor punt 5 willen weten kijken we er als vorige punt bij punt 5 gemarkeerd staat. Het vorige punt is 6, daarna kijken we bij punt 6, die heeft als voorganger punt 3. Punt 3 heeft als voorganger punt 1, en zo zijn we bij het startpunt.
% subsubsection resultaat (end)

% subsection dijkstra (end)

\subsection{Bellman Ford} % (fold)
\label{sub:belman_ford}
Het Bellman Ford algoritme is een algoritme dat de kortste paden in een netwerk van \'e\'en node naar andere nodes uitrekent. 

Het Bellman Ford algoritme staat, in tegenstelling tot het algoritme van Dijkstra, wel negatieve edges toe in een graaf. Negatieve cycles (cycles waarvan alle edges samen negatief zijn) mogen voorkomen, maar in dat geval zal er geen afstand worden uitgerekend. Het algoritme zal dan aangeven dat er geen afstand berekend kan worden.

\subsubsection{werking} % (fold)
\label{ssub:werking_belman_ford}
\begin{itemize}
	\item In de initialisatie toestand krijgt de source node de kosten: 0. Alle andere nodes hebben kosten $\infty$.
	\item Eerst worden de kosten naar de buren bepaald. Vervolgens wordt volgens een iteratief proces de minimale kosten naar elke edge berekend. Als er N nodes zijn, zal dit N-1 keer moeten gebeuren. Het aftrekken van 1 is omdat de source node zijn eigen afstand al weet.
	\item Alle gevonden paden worden typisch in een (routing) tabel opgeslagen, met als kolommen z'n buren en als rijen de mogelijke bestemmingen.
\end{itemize}

In Figuur~\ref{fig:bellmanford} lengte naar de source is 0 en de rest is oneindig. 
\begin{figure}[htb]
\begin{center}
\includegraphics[width=0.4\textwidth]{./images/bellmanford}
\caption{}
\label{fig:bellmanford}
\end{center}
\end{figure}

Van elk mogelijke bestemming wordt volgens in Figuur~\ref{fig:bellmanford2} een iteratief proces de kortste afstand bepaald. Elk pad wordt onderzocht. $(4-1 = 3x)$
\begin{figure}[htb]
\begin{center}
\includegraphics[width=0.4\textwidth]{./images/bellmanford2}
\caption{}
\label{fig:bellmanford2}
\end{center}
\end{figure}
% subsubsection werking (end)

% subsection belman_ford (end)

\subsection{Johnsons} % (fold)
\label{sub:johnsons}
Johnson’s algoritme wordt gebruikt om de korste paden tussen iedere paren van knopen te vinden. Het algoritme is dus een \emph{APSP-algortime} (All Pair Shortest Path).  
Het algoritme wordt gebruikt voor het all-pair probleem voor  zogeheten gerichte ‘sparse graphs’  (schaarse grafen). Een schaarse graaf is een graaf met ongeveer evenveel zijden als knopen.  Dus als $G = (V, E)$ een graaf is, is het schaars als $|E| = O|V|$. Dat wil zeggen dat de hoeveelheid zijden hoogstens van dezelfde orde is als de hoeveelheid knopen. 
Johnson’s algoritme laat zijden met negatieve gewichten toe, maar er mogen geen negatieve cycles bestaan. Dit komt, omdat Johnson’s algoritme gebruik maakt van Dijkstra’s algoritme om van iedere paar van knopen het kortse pad te vinden.

\subsubsection{Werking} % (fold)
\label{ssub:werking_johnsons}
Het algortime werkt als volgt:

\begin{enumerate}
	\item Als eerst wordt er een nieuwe knoop q  toegevoegd aan de graaf. Knoop q is verbonden met iedere andere knoop in de graaf. De zijden van q  hebben waarde 0 als gewicht en zijn naar de andere knopen gericht.
	\item Vervolgens wordt het Bellman-Ford algortime gebruikt om een kortse pad te vinden van q naar iedere andere knoop v genaamd $h(v)$.  Als tijdens de uitvoer van Bellman-Ford een negatieve cycle word gevonden, stopt het Johnson’s algortime.
	\item Als er geen negatieve cycle aanwezig is in de graaf, dan worden de gewichten van de zijden opnieuw berekend. Bijvoorbeeld een zijde van u naar v met gewicht $w(u, v)$ krijgt een nieuw gewicht $w(u, v) = w(u, v) + h(v) – h(u)$. Dus het nieuwe gewicht van de zijde is het oude gewicht plus het korste pad naar v min het korste pad naar u.
	\item Als laatste wordt q verwijderd van de graaf en wordt Dijkstra’s algortime  gebruikt om de kortste paden van ieder uniek paar te vinden.
\end{enumerate}
Johnson’s algortime maakt dus gebruik van Bellman-Ford om negatieve cycles te detecteren en om de zijden nieuwe waarden te geven die positief zijn. Als dat eenmaal gelukt is, wordt er gebruik gemaakt van Dijkstra’s algortime om de korste paden te vinden tussen ieder paar van knopen.

% subsubsection werking (end)

\subsubsection{Pseudo-code} % (fold)
\label{ssub:pseudo_code_johnsons}
\begin{lstlisting}[label=pseudo_code_johnsons, caption=Johnsons Algoritme Pseudo-code]
Maak knoop q aan

Maak zijden aan met gewicht 0 van q naar iedere andere knoop

Voor elke knoop v in G
	Doe Bellman-Ford vanuit v

	Als er een negatieve cycle is
		Stop met alles

Voor elke zijde e=(u,v) in G
	Nieuw gewicht e  = oude gewicht e + korste pad naar v – korste pad naar u

Verwijder knoop q

Verwijder zijden van knoop q

Voor elke knoop v in G
	Doe Dijkstra’s vanuit v

\end{lstlisting}

% subsubsection pseudo_code (end)

% subsection johnsons (end)

\subsection{Floyd Warshall} % (fold)
\label{sub:floyd_warshall}
Floyd-Warshall is een algoritme om het kortste pad in een gewogen graaf te vinden. Het algoritme berekent de de kortste paden (opgetelde gewichten van de zijden) van alle combinaties van knopen. Het Floyd-Warshall algoritme geeft niet de details van de kortste paden terug.

Het algoritme werkt door voor twee willekeurige punten het kortste pad te berekenen via elk punt. Dus, stel dat er een graaf G is met knopen V, genummerd van 1 tot N. Dan wordt er voor twee willkeurige punten, i en j, gekeken naar het korste pad dat gebruik maakt van knoop k. k is vervolgens een knoop uit de set ${1,2,..k}$. Het algoritme berekent vervolgens voor elke i tot elke j het kortste pad via k.

\subsubsection{Pseudo-code} % (fold)
\label{ssub:pseudo_code_floyd_warshall}
D is een matrix met de lengtes tussen alle knopen. Na uitvoering van het algoritme zal $D[i,j]$ de lengte van het kortste pad van knoop i naar knoop j bevatten.

In de initalisatie stap wordt er gekeken of er een verbinding is tussen elke knoop i en elke knoop j. Als er een direct verbinding is tussen de knopen dan wordt het gewicht van die zijde opgeslagen in de matrix en als er geen verbinding bestaat kan er b.v. oneindig worden teruggegeven en opgeslagen in de matrix.
\begin{lstlisting}[label=pseudo_code_floyd_warshall, caption=Pseudo-code Floyd Warshall deel 1]
voor alle knopen i: 
	voor alle knopen j:
		D[i,j] = weight(i,j)
		
\end{lstlisting}
Zo ook kunnen we in de initalisatie al zeggen dat van elke knoop i naar zichzelf de afstand 0 is.
\begin{lstlisting}[label=pseudo_code_floyd_warshall2, caption=Pseudo-code Floyd Warshall deel 2]
voor alle knopen i:
	D[i,i] = 0
\end{lstlisting}
Na de initalisatie kunnen alle knopen worden doorlopen. Als buitenste lus worden de knopen genomen die als tussenstappen gaan dienen. Voor elke knoop als tussenstap wordt er gekeken of er pad bestaat tussen i en j via k en of dat pad korter is dan het huidige pad in de matrix.
\begin{lstlisting}[label=pseudo_code_floyd_warshall3, caption=Pseudo-code Floyd Warshall deel 3]
voor all knopen k:
	voor alle knopen i: 
		voor alle knopen j:
			D[i,j] = min (D[i,j], D[i,k] + D[k,j])
\end{lstlisting}
Als het algoritme door alle knopen is geweest zal de matrix alleen nog de kortste paden tussen de combinatie van knopen bevatten.

% subsubsection pseudo_code (end)

% subsection floyd_warshall (end)

\subsection{Depth First} % (fold)
\label{sub:depth_first}
Het Depth First zoek algoritme is een zoekmethode waarbij vanaf een begin knoop (wortel) zo lang mogelijk een dieperliggende knoop wordt bezocht. Als nog niet is voldaan aan de zoekopdracht en een knoop zonder dieperliggende knopen wordt bezocht, wordt terug gegaan naar een knoop waar nog niet alle dieperliggende knopen zijn bezocht.

\begin{figure}[htb]
\begin{center}
\includegraphics[width=0.4\textwidth]{./images/depthfirst}
\caption{}
\label{fig:depthfirst}
\end{center}
\end{figure}

\subsubsection{Pseudo-code} % (fold)
\label{ssub:pseudo_code_depth_first}

De pseudo-code lijkt sterk op Breadth First (zie Paragraaf~\ref{sub:breadth_first} ) het algoritme. De agenda bestaat in het Depth First zoekalgoritme echter uit een \textbf{stack}.

\begin{lstlisting}[label=pseudo_code_depth_first, caption=Depth first Pseudo-code]
agenda.create *
markeer vanaf 
agenda.put(vanaf) 

while (not agenda.empty) { 
	afspraak = agenda.get
	agenda.remove 
	verwerk zoekopdracht 
	voor alle ongemarkeerde buurknopen k van afspraak { 
		markeer k 
		agenda.put(k) 
	} 
}
\end{lstlisting}

% subsubsection pseudo_code (end)

% subsection depth_first (end)

\subsection{Breadth First} % (fold)
\label{sub:breadth_first}
Het Breadth First zoek algoritme is een zoekmethode waarbij vanaf een begin knoop  alle nabijgelegen knopen worden doorzocht. Van iedere nabijgelegen knoop wordt vervolgens opnieuw iedere, nog niet bezochte, nabijgelegen node doorzocht. Dit blijft zich herhalen tot voldaan is aan de zoekopdracht.

\begin{figure}[htb]
\begin{center}
\includegraphics[width=0.4\textwidth]{./images/breadthfirst}
\caption{}
\label{fig:breathfirst}
\end{center}
\end{figure}

\subsubsection{Pseudo-code} % (fold)
\label{ssub:pseudo_code_breadth_first}
De pseudo-code lijkt sterk op depth first algoritme (zie paragraaf~\ref{sub:depth_first}). De agenda bestaat in het Breadth First zoekalgoritme echter uit een \textbf{queue}.

\begin{lstlisting}[label=pseudo_code_breadth_first, caption=Breadth first Pseudo-code]
agenda.create *
markeer vanaf 
agenda.put(vanaf) 

while (not agenda.empty) { 
	afspraak = agenda.get
	agenda.remove 
	verwerk zoekopdracht 
	voor alle ongemarkeerde buurknopen k van afspraak { 
		markeer k 
		agenda.put(k) 
	} 
}
\end{lstlisting}
% subsubsection pseudo_code (end)
% subsection breadth_first (end)
% section graaf_algoritmen (end)
% chapter standaaralgoritmen (end)

\chapter{Projectgerelateerde algoritmen} % (fold)
\label{cha:Project_gerelateerde_algoritmen}

\section{First Fit (Decreasing)} % (fold)
\label{sec:first_fit_decreasing}

First fit is een algoritme voor het oplossen van het bin-packing probleem. Het bin-packing probleem houdt zich bezig met het vullen van zogenaamde \emph{bins}. Een bin is een container met een van tevoren bepaalde beperkte inhoud. Deze bins worden gevuld met een van tevoren bepaald aantal blokken. Deze blokken moeten van verschillende grootte zijn en dus verschillende hoeveelheid aan ruimte innemen in een bin.

Bij het oplossen van het bin-packing probleem is het van belang dat er zo weinig mogelijk bins in het gebruik zijn wanneer alle blokken in de bins zijn gestopt. First fit is \'e\'en van de oplossingen voor het bin-packing probleem.

\begin{figure}[hb!]
\begin{center}
\includegraphics[width=0.5\textwidth]{./images/firstfit}
\caption{}
\label{fig:firstfit}
\end{center}
\end{figure}

In Figuur~\ref{fig:firstfit} zie een reeks binbinss naast elkaar. De witte vierkanten met een getal in het midden zijn de blokken van verschillende grootte. 

\subsection{Werking van het algoritme} % (fold)
\label{sub:werking_van_het_algoritme}

Het first fit algoritme probeert per blok de eerste bin te vullen. Vandaar de naam first fit.
Het zoeken naar een plaats voor het blok begint vanaf het begin van bins. Zodra er een geschikte bin is gevonden, wordt het blok erin gestopt en is het volgende blok aan de beurt. Als er geen plaats meer is voor het blok, dan wordt er een nieuwe bin aangemaakt en wordt daar het blok in gestopt. Dit gaat zo door totdat alle blokken op zijn.

Hieronder de pseudocode voor First Fit.

\begin{lstlisting}[label=first_fit_pseudocode, caption=First fit pseudocode]
while(er zijn nog blokken) {
	pak het volgende blok;
	begin bij de eerste bin;
	while(blok niet weggestopt en er zijn nog bins) {
		if(blok past in de bin) {
			stop blok in de bin;
		}
		pak de volgende bin;
	}
	if(blok nog niet weggestopt) {
		maak nieuwe bin aan;
		stop blok in de bin;
  	}
}
\end{lstlisting}
% subsection werking_van_het_algoritme (end)

\subsection{First Fit Decreasing} % (fold)
\label{sub:first_fit_decreasing}
Een variatie op First Fit is First Fit Decreasing. Het is in principe hetzelfde algoritme als First Fit met een initi\"ele handeling voorafgaand aan het wegstoppen van de blokken, namelijk het sorteren van de blokken op aflopende volgorde, het grootste blok wordt dan als eerst behandeld. 

Er hoeft maar \'e\'en regel pseudocode toegevoegd te worden aan de de pseudocode van First Fit, namelijk:
\begin{lstlisting}[label=first_fit_decreasing_pseudocode,caption=First fit decreasing pseudocode]
sorteer de blokken in aflopende volgorde;
\end{lstlisting}
Hierdoor is First Fit Decreasing een stuk effici\"enter dan First Fit.
% subsection first_fit_decreasing (end)

% section first_fit_decreasing_ (end)

\section{Best Fit (Decreasing)} % (fold)
\label{sec:best_fit_decreasing_}
Best fit is een algoritme voor het oplossen van het bin-packing probleem. Voor meer uitleg over het bin-packing probleem zie paragraaf~\ref{sec:first_fit_decreasing}.
\subsection{Werking van het Best Fit Algoritme} % (fold)
\label{sub:werking_van_het_best_fit_algoritme}
Best Fit probeert een blok in een bin te plaatsen waar deze past en zo weinig mogelijk ruimte achter laat. Als er een nieuw blok ingevoegd moet worden, worden alle beschikbare bins doorlopen en gekeken of er nog plaats is om het huidige blok in te voegen. Van alle bins waar ruimte is voor het huidige blok wordt gekeken wat de minimale ruimte is die overblijft na plaatsing en de bin waar de minste ruimte over blijft wordt gekozen. Als de ruimte die over is in de bin precies de grootte is van het blok dan wordt het blok ook geplaatst. De minimale ruimte die overblijft na plaatsing kan dus ook 0 zijn, het blok past dan nog precies in de bin. Als het blok niet meer in de gevulde bins past wordt er een nieuwe bin aangemaakt.
% subsection werking_van_het_best_fit_algoritme (end)
\subsection{Voorbeeld} % (fold)
\label{sub:voorbeeld_best_fit}
Volgens onderstaande stappen wordt de lijst [3,4,8,4,1] in bins van grootte 10 geplaatst
\begin{enumerate}
\item \textbar0\textbar
\item \textbar3\textbar
\item \textbar7\textbar
\item \textbar7\textbar \textbar8\textbar
\item \textbar7\textbar \textbar8\textbar \textbar4\textbar
\item \textbar7\textbar \textbar9\textbar \textbar4\textbar
\end{enumerate}
% subsection voorbeeld (end)
\subsection{Psuedocode} % (fold)
\label{sub:psuedocode}
\begin{lstlisting}[label=best_fit_pseudocode,caption=Best fit pseudocode]
while(er zijn nog blokken) {
	pak het volgende blok;
	while(er zijn nog bins)
	{
		pak de volgende bin;
		if(blok past in de bin) {
			if(ruimte na plaatsing het kleinste is tot dan toe){
				sla ruimte en bin op
			}
		}
	}	
	if(ruimte is gevonden in de bins) {
		plaats het blok in de bin met de kleinste ruimte na plaatsing
	} else {
		if(blok nog niet weggestopt) {
			maak nieuwe bin aan;
			stop blok in de bin;
		}
	}
}
\end{lstlisting}

% subsection psuedocode (end)
\subsection{Best Fit Decreasing} % (fold)
\label{sub:best_fit_decreasing}
Best Fit wordt Best Fit Decreasing door de blokken van te voren te sorteren in grootte van groot naar klein. Vervolgens wordt het algoritme op de lijst met aflopende grootte van blokken toegepast.
% subsection best_fit_decreasing (end)
% section best_fit_decreasing_ (end)

\section{Next Fit} % (fold)
\label{sec:next_fit}
Next Fit is een algoritme voor het oplossen van het bin-packing probleem. Voor meer uitleg over het bin-packing probleem zie paragraaf~\ref{sec:first_fit_decreasing}
\subsection{Werking van het Next Fit Algoritme} % (fold)
\label{sub:werking_van_het_next_fit_algoritme}
Het Next Fit algoritme zal proberen de blokken uit een lijst, \'e\'en voor \'e\'en en op volgorde van de lijst, te plaatsen in de huidige openstaande bin. Wanneer het huidige blok niet in de huidige bin past, zal de bin worden gesloten en zal een nieuwe bin geopend worden.
% subsection werking_van_het_next_fit_algoritme (end)
\subsection{Voorbeeld} % (fold)
\label{sub:voorbeeld_next_fit}
Stel we hebben een lijst met blokken met grootte [3, 6, 2, 1, 5, 7] en we plaatsen deze in bins van grootte 10, dan gaat het algoritme als volgt:
\begin{enumerate}
\item Blok met grootte 3 past in de bin met grootte 10. De bin heeft nog 7 ruimte over.
\item Blok met grootte 6 past in de bin met grootte 10 en vrije ruimte 7. De bin heeft nu nog 1 ruimte over.
\item Blok met grootte 2 past niet in de huidige bin, dus wordt deze gesloten en een nieuwe bin geopend. Vervolgens wordt het blok met grootte 2 hierin geplaatst. Deze bin heeft nog 8 ruimte over.
\item Blok met grootte 1 past in de bin met grootte 10 en vrije ruimte 8. Deze bin heeft nu nog 7 ruimte over.
\item Blok met grootte 5 past in de bin met grootte 10 en vrije ruimte 7. Deze bin heeft nu nog 2 ruimte over.
\item Blok met grootte 7 past niet in de huidige bin, dus wordt deze gesloten en een nieuwe bin geopend. Vervolges wordt het blok met grootte 7 hierin geplaatst. Deze bin heeft nog 3 ruimte over.
\end{enumerate}

Uiteindelijk heeft het Next Fit algoritme de 6 blokken in 3 bins geplaatst.
% subsection voorbeeld (end)
% section next_fit (end)

\section{Last Fit} % (fold)
\label{sec:last_fit}
Het algoritme last fit is een bin packing algoritme. Bij dit probleem heeft men een aantal containers met beperkte ruimte, waar men objecten van een bepaalde grootte in kan stoppen. In de ideale situatie heeft men zo weinig mogelijk containers in gebruik.
\subsection{Werking van het Last Fit Algoritme}% % (fold)
\label{sub:werking_van_het_last_fit_algoritme_}
Het last fit algoritme plaatst zijn aangeboden objecten in de laatste container met genoeg beschikbare ruimte. Wanneer men een set containers ordent van links naar rechts, kan  men de meest linkse container als het begin en de meest rechtse container als het eind zien. In deze situatie werkt het algoritme de containers van rechts naar links af. 
% subsection werking_van_het_last_fit_algoritme_ (end)
\subsection{Pseudo-code} % (fold)
\label{sub:pseudocode}
\begin{lstlisting}[label=last_fit_pseudocode,caption=Last fit pseudo-code]
while(er zijn nog blokken) { 
	pak het volgende blok	
	if(er zijn nog bins) {
		pak de laatste bin;
	}
	while(blok niet weggestopt en er zijn nog bins) {		
		if(blok past in de bin) {
			stop blok in de bin
		}
		pak de vorige bin		
	}
	if(blok nog niet weggestopt) {
		maak nieuwe bin aan;
		stop blok in de bin; 
	}
}
\end{lstlisting}
% subsection pseudocode (end)
% section last_fit (end)

\section{Worst Fit} % (fold)
\label{sec:worst_fit}
Worst fit is een algoritme voor het oplossen van het bin-packing probleem. Voor meer uitleg over het bin-packing probleem zie paragraaf~\ref{sec:first_fit_decreasing}.
\subsection{Werking van het Worst Fit Algoritme} % (fold)
\label{sub:werking_van_het_worst_fit_algoritme}
Worst Fit probeert een blok in een bin te plaatsen waar deze past en zo veel mogelijk ruimte achter laten. Als er een nieuw blok ingevoegd moet worden, worden alle beschikbare bins doorlopen en gekeken of er nog plaats is om het huidige blok in te voegen. Van alle bins waar genoeg ruimte over is voor het huidige blok wordt gekeken wat de maximale ruimte is die overblijft na plaatsing en de bin waar de meeste ruimte over blijft wordt gekozen. Als het blok niet meer in de gevulde bins past wordt er een nieuwe bin aangemaakt.
% subsection werking_van_het_worst_fit_algoritme (end)
\subsection{Voorbeeld} % (fold)
\label{sub:voorbeeld_worst_fit}
Volgens onderstaande stappen wordt de lijst `[3,4,8,4,1]` in bins van grootte 10 geplaatst
\begin{enumerate}
\item \textbar0\textbar
\item \textbar3\textbar
\item \textbar7\textbar
\item \textbar7\textbar \textbar8\textbar
\item \textbar7\textbar \textbar8\textbar \textbar4\textbar
\item \textbar7\textbar \textbar8\textbar \textbar5\textbar
\end{enumerate}

% subsection voorbeeld (end)
\subsection{Psuedocode} % (fold)
\label{sub:psuedocode_worst_fit}
\begin{lstlisting}[label=worst_fit_pseudocode,caption=Worst fit pseudocode]
while(er zijn nog blokken) {
	pak het volgende blok;
	while(er zijn nog bins) {
		pak de volgende bin;
		if(blok past in de bin) {
			if(ruimte na plaatsing het grootste is tot dan toe) {
				sla ruimte en bin op
			}
		}
	}
	if(ruimte is gevonden in de bins) {
		plaats het blok in de bin met de grootste ruimte na plaatsing
	} else if(blok nog niet weggestopt) {
    	maak nieuwe bin aan;
    	stop blok in de bin;
  	}
  }
}
\end{lstlisting}
% subsection psuedocode (end)

\subsection{Worst Fit Decreasing} % (fold)
\label{sub:worst_fit_decreasing}
Worst Fit wordt Worst Fit Decreasing door de blokken van te voren te sorteren in grootte van groot naar klein. Vervolgens wordt het algoritme op de lijst met aflopende grootte van blokken toegepast.
% subsection worst_fit_decreasing (end)
% section worst_fit (end)

\section{Almost Worst Fit} % (fold)
\label{sec:almost_worst_fit}
Worst fit is een algoritme voor het oplossen van het bin-packing probleem. Voor meer uitleg over het bin-packing probleem zie paragraaf~\ref{sec:first_fit_decreasing}.
\subsection{Werking van het Almost Worst Fit Algoritme} % (fold)
\label{sub:werking_van_het_almost_worst_fit_algoritme}
Worst Fit probeert een blok in een bin te plaatsen waar deze past en op \'e\'en na zo veel mogelijk ruimte achter laten. Als er een nieuw blok ingevoegd moet worden, worden alle beschikbare bins doorlopen en gekeken of er nog plaats is om het huidige blok in te voegen. Van alle bins waar genoeg ruimte over is voor het huidige blok wordt gekeken wat de maximale ruimte is die overblijft na plaatsing en de bin waar de op \'e\'en na meeste ruimte over blijft wordt gekozen. Als het blok niet meer in de gevulde bins past wordt er een nieuwe bin aangemaakt.
% subsection werking_van_het_almost_worst_fit_algoritme (end)
\subsection{Voorbeeld} % (fold)
\label{sub:voorbeeld}
Volgens onderstaande stappen wordt de lijst `[3,4,8,4,1]` in bins van grootte 10 geplaatst.
\begin{enumerate}
\item \textbar0\textbar
\item \textbar3\textbar
\item \textbar7\textbar
\item \textbar7\textbar \textbar8\textbar
\item \textbar7\textbar \textbar8\textbar \textbar4\textbar
\item \textbar8\textbar \textbar8\textbar \textbar4\textbar
\end{enumerate}

% subsection voorbeeld (end)
\subsection{Psuedocode} % (fold)
\label{sub:psuedocode_almost_fit}
\begin{lstlisting}[label=almost_fit_pseudocode,caption=Almost fit pseudocode]
while(er zijn nog blokken) { 
	pak het volgende blok;
	while(er zijn nog bins) {
		pak de volgende bin;
		if(blok past in de bin) {
			if(ruimte na plaatsing het op \'e\'en na grootste is tot dan toe) {
				sla ruimte en bin op
			}
		}
	} 
	if(ruimte is gevonden in de bins) {
		plaats het blok in de bin met de grootste ruimte na plaatsing
	} else if(blok nog niet weggestopt) {
		maak nieuwe bin aan;
		stop blok in de bin;
	}
}
\end{lstlisting}
% subsection psuedocode (end)
% section almost_worst_fit (end)
% chapter onderzoek (end)

\chapter{Datastructuur} % (fold)
\label{cha:datastructuur}
De datastructuur gebruikt om de bin-packing algoritmen te implementeren en te analyseren wordt gerepresenteerd in Figuur~\ref{fig:datastructuur}.
\begin{figure}[hb!]
\begin{center}
\includegraphics[width=0.25\textwidth]{./images/datastructuur}
\caption{}
\label{fig:datastructuur}
\end{center}
\end{figure}

De klasse BinContainer beheerd een lijst met Bin-objecten. Iedere Bin-object bevat een lijst waar Block-objecten in kunnen. De Block-objecten zijn de objecten die door de bin-packing algoritmen worden ingepakt in de Bin-objecten.
\section{Block} % (fold)
\label{sec:datastructuur_block}
Een Block-object is een object dat ruimte in beslag neemt in een Bin-object. Block-objecten zijn dus de objecten die in de bins gepakt moeten worden door de bin-packing algoritmen. Een block heeft een grootte dat aangeeft hoeveel ruimte het in beslag neemt. De grootte is uitgedrukt in een geheel getal boven nul.
% section block (end)
\section{Bin} % (fold)
\label{sec:datastructuur_bin}
Een Bin-object wordt gebruikt om de blocks in te pakken. Iedere Bin heeft een maximale inhoud. De grootte is eveneens uitgedrukt in een geheel getal boven nul, net als bij een Block. Een Bin heeft naast een maximale inhoud ook een huidige inhoud. De huidige inhoud wordt bepaald door de grootten van de Blocks die in de Bin zitten. De huidige inhoud is dus de optelsom van de grootten van de Blocks die in de Bin zitten. Deze huidige inhoud mag niet groter zijn dan de maximale inhoud. Op deze manier is het aantal Block-objecten niet van belang, maar de ruimte die de Block-objecten gezamelijk innemen van belang.
% section bin (end)
\section{Bin Container} % (fold)
\label{sec:datastructuur_bin_container}
De BinContainer is het omvattend object van de datastructuur. Aan de BinContainer kunnen Bins worden toegevoegd en in de Bins kunnen Blocks worden gepakt. Er is geen beperking aan het aantal Bins dat een BinContainer kan bevatten.
% section bin_container (end)
\section{Gebruik Datastructuur} % (fold)
\label{sec:datastructuur_gebruik_datastructuur}
Iedere implementatie van een bin-packing algoritme maakt gebruikt van de datastructuur.  Het gebruik van de datastructuur verschilt een klein beetje per algoritme, maar in grote lijnen is het Blocks in Bins pakken totdat de Blocks allemaal ingepakt zijn. Hoe dat precies gebeurt verschilt dus per algoritme. Om te laten zien hoe de datastructuur word gebruikt, word het algoritme First Fit als voorbeeld genomen. Hieronder zie je de code dat wordt uitgevoerd om het bin-packing probleem op te lossen volgens het First Fit algoritme.

\begin{lstlisting}[label=datastructuur_pseudocode,caption=Gebruik Datastructuur]
while(blocks.size() > 0) {
	Block block = blocks.remove(0);
	int binIndex = 0;
	while( binIndex < binContainer.getBins().size() ){
		Bin bin = binContainer.getBins().get(binIndex);
		if(bin.storageAvailable( block.getSize() ) ){
			bin.addBlock( block );
			block.place();
			break;
			} else {
				binIndex++;
			}
		}
	if( !block.isPlaced() ) {
		Bin bin = new Bin(binSize);
		bin.addBlock( block );
		block.place();
		binContainer.addBin( bin );
	}
}
\end{lstlisting}

Blocks is de lijst met Block-objecten die van tevoren wordt gevuld. First Fit blijft doorgaan totdat de lijst met Blocks leeg is. Voor ieder Block wordt gekeken of er een Bin beschikbaar is met voldoende ruimte in de BinContainer. De Bins worden één voor één uit de BinContainer gehaald.  Als er een Bin is met voldoende ruimte, dan wordt de Block erin gepakt en is het volgende Block aan de beurt. Als er geen Bin meer is met voldoende ruimte dan wordt er een nieuwe lege bin aan de BinContainer toegevoegd. 
% section gebruik_datastructuur (end)

% chapter datastructuur (end)

\chapter{Analyse} % (fold)
\label{cha:analyse}
Om de verschillende algoritmes te vergelijken hebben we het aantal bins dat na plaatsing van alle blokken in gebruik is bijgehouden. Ook de executietijd van het algoritme hebben we meegenomen.

Voor elke doorloop van het algoritme wordt er een bestand gecre\"eeerd waarin 10.000 willekeurige getallen worden weggeschreven. Deze file wordt vervolgens gebruikt om een lijst met blokken aan te maken. Deze blokken worden voor elk algoritme gebruikt. Bij een tweede doorloop wordt weer een nieuw bestand gecre\"eerd met weer 10.000 willekeurige getallen. Een doorloop is het eenmaal uitvoeren van alle algoritmes op de lijst met blokken.

We hebben 9 doorlopen doorgevoerd, dus alle algoritmes worden 9 keer uitgevoerd op een set van 10.000 willekeurige getallen. Het resultaat is hieronder opgesteld:


\section{Resultaten} % (fold)
\label{sec:resultaten}

\begin{table}[htb]
	\begin{center}
		\begin{tabular}{|c|c|c|c|}
			\hline
			\textbf{Algoritme} &\textbf{Bins used}&\textbf{Executed (ms)}\\\hline
			First Fit &5099&287.66\\ 
				&5103&299.37\\
				&5050&249.61\\
				&5112&264.69\\
				&5187&279.7\\
				&5108	&291.55\\
				&5162	&309.89\\
				&5158	&268.08\\
				&5181	&273.33\\ \hline
			\textbf{Gemiddeld:}&5128.888889&280.4311111\\ \hline
		\end{tabular}
	\end{center}
	\label{table:analyse_first_fit}
	\caption{Resultaten meting First Fit}
\end{table}


\begin{table}[htb]
	\begin{center}
		\begin{tabular}{|c|c|c|c|}
			\hline
			\textbf{Algoritme} &\textbf{Bins used}&\textbf{Executed (ms)}\\\hline
			First Fit Decreasing & 4981 & 25.78 \\
				&5022&	332.1\\
				&4969&	345.15\\
				&5011&	330.65\\
				&5105&	351\\
				&5010&	352.21\\
				&5065&	358.46\\
				&5050&	370.62\\
				&5057&	345.71\\ \hline
			 \textbf{Gemiddeld:} & 5030 & 345.7422222 \\ \hline

		\end{tabular}
	\end{center}
	\label{table:analyse_first_fit_decr}
	\caption{Resultaten meting First Fit Decreasing}
\end{table}

\begin{table}[htb]
	\begin{center}
		\begin{tabular}{|c|c|c|c|}
			\hline
			\textbf{Algoritme} &\textbf{Bins used}&\textbf{Executed (ms)}\\\hline
			Best Fit&5054&168.78\\
				&5049&166.54\\
				&5000&165.67\\
				&5055&165.24\\
				&5136	&169.26\\
				&5069	&172.92\\
				&5121	&165.07\\
				&5110	&167.06\\
				&5141	&179.06\\ \hline
			\textbf{Gemiddeld:} & 5081.666667 & 168.8444444\\ \hline
		\end{tabular}
	\end{center}
	\label{table:analyse_best_fit}
	\caption{Resultaten meting Best Fit}
\end{table}

\begin{table}[htb]
	\begin{center}
		\begin{tabular}{|c|c|c|c|}
			\hline
			\textbf{Algoritme} &\textbf{Bins used}&\textbf{Executed (ms)}\\\hline
			Almost Worst Fit &	5449&	181.36\\
				&5467&	188.14\\
				&5405&	178.54\\
				&5473&	184.66\\
				&5527&	187.28\\
				&5472&	179.42\\
				&5519&	186.52\\
				&5509&	184.03\\
				&5511&	195.43\\ \hline
			\textbf{Gemiddeld:} &	5481.333333	& 185.0422222 \\ \hline
		\end{tabular}
	\end{center}
	\label{table:analyse_worst_fit}
	\caption{Resultaten meting Worst Fit}
\end{table}

\begin{table}[htb]
	\begin{center}
		\begin{tabular}{|c|c|c|c|}
			\hline
			\textbf{Algoritme} &\textbf{Bins used}&\textbf{Executed (ms)}\\\hline
			Next Fit&	6599&	63.21\\
				&6608	&52.52\\
				&6596	&78.6\\
				&6643	&51.05\\
				&6685	&51.08\\
				&6633	&53.16\\
				&6711	&53.79\\
				&6655	&51.67\\
				&6662	&53.63\\ \hline
			\textbf{Gemiddeld:} &	6643.555556	& 56.52333333 \\ \hline
		\end{tabular}
	\end{center}
	\label{table:analyse_next_fit}
	\caption{Resultaten meting Next Fit}
\end{table}

\begin{table}[htb]
	\begin{center}
		\begin{tabular}{|c|c|c|c|}
			\hline
			\textbf{Algoritme} &\textbf{Bins used}&\textbf{Executed (ms)}\\\hline
			Last Fit&	5553	&186.13\\
			 &5568	&191.99\\
			 &5500	&172.32\\
			 &5559	&178.38\\
			 &5616	&188.2\\
			 &5557	&178.69\\
			 &5616	&179.68\\
			 &5590	&176.83\\
			 &5609	&192.19\\ \hline
			\textbf{Gemiddeld:} &	5574.222222 & 182.7122222 \\ \hline
		\end{tabular}
	\end{center}
	\label{table:analyse_last_fit}
	\caption{Resultaten meting Last Fit}
\end{table}

% section resultaten (end)

\clearpage

\section{Conclusies} % (fold)
\label{sec:conclusies}
Uit bovenstaande resultaten is een sortering gemaakt op basis van gebruikte bins en executietijd:
Gesorteerd op basis van bins used

\begin{table}[htb]
	\begin{center}
		\begin{tabular}{|c|c|c|c|}
			\hline
			\textbf{Algoritme} &\textbf{Bins used}&\textbf{Executed (ms)}\\\hline
			First Fit Decreasing	& 5030	 &	346 \\
			Best Fit			&5082	&	169\\
			First Fit			&5129	&	280\\
			Almost Worst Fit		&5481	&	185\\
			Last Fit			&5574	&	183\\
			Worst Fit			&5841	&	202\\
			Next Fit			&6644	&	57\\ \hline
		\end{tabular}
	\end{center}
	\label{table:conclusions_bins_used}
	\caption{Algoritmes gesorteerd op gemiddelde bins used}
\end{table}

Aan de hand van het aantal bins in gebruik na plaatsing van alle blokken blijkt First Fit Decrasing het meest effici\"ente algoritme, op basis van ruimte inname, te zijn. First Fit Decreasing is echter niet volledig eerlijk ten opzichte van de andere algoritmes aangezien dit algoritme de lijst met blokken eerst sorteert op aflopende volgorde terwijl de andere geteste algoritmes dit niet doen.

Van de algoritmes zonder vooraf sorteren is Best Fit het meest effici\"ent op gebied van bin gebruik. We hadden van te voren verwacht dat Best Fit ook het meest effici\"ent met de ruimte om zou gaan aangezien dit algoritme zo weinig mogelijk ruimte probeert over te houden in een bin na plaatsing van een blok. het zoekt de bin op waar het minste ruimte over blijft na plaatsing van een blok.

\begin{table}[htb]
	\begin{center}
		\begin{tabular}{|c|c|c|c|}
			\hline
			\textbf{Algoritme} &\textbf{Bins used}&\textbf{Executed (ms)}\\\hline
			Next Fit		&	57	&	6644\\
			Best Fit		&	169	&	5082\\
			Last Fit		&	183	&	5574\\
			Almost Worst Fit	&	185	&	5481\\
			Worst Fit		&	202	&	5841\\
			First Fit		&	280	&	5129\\
			First Fit Decreasing	&346		&5030\\ \hline
		\end{tabular}
	\end{center}
	\label{table:conclusions_execution_time}
	\caption{Algoritmes gesorteerd op gemiddelde executie tijd}
\end{table}

Aan de hand van de doorlooptijd van het algoritme voor het plaatsen van alle blokken in de bins bleek Next Fit het snelste. Wij hadden ook verwacht dat Next Fit het snelste was, aangezien dit algoritme niet terug kijkt naar de bins die eerder al gevuld waren. Zodra een bin vol is maakt dit algoritme een nieuwe bin aan en gaat verder. De andere geteste algoritmes kijken ook terug naar de bins die al gevuld zijn en zijn daarom langzamer dan Next Fit.

Opmerkelijk is dat Best Fit na Next Fit het snelste algoritme blijkt te zijn. Best Fit was van de algoritmes zonder sortering het meest effici\"ent qua ruimtegebruik en na verwachting zou het ook één van de langzamere algoritmes zijn. Het algoritme loopt immers door alle bins en kijkt voor elke bin waar het minste ruimte overblijft na plaatsing. Als alle bins doorlopen zijn wordt de bin gekozen waar het minste ruimte overbleef. First Fit moet ook door alle bins doorlopen maar kiest de eerste bin waar het blok in past. Na verwachting zou First Fit sneller moeten zijn dan Best Fit maar aan de hand van de resultaten blijkt dit niet zo te zijn. Een mogelijke reden voor dit verschil kan zijn dat er in de implementatie verschillen zitten waardoor de snelheid van het algoritme niet optimaal is.

% section conclusies (end)


% chapter analyse (end)

\chapter{Conclusie} % (fold)
\label{cha:conclusie}
Uit onze resultaten blijkt dat Best Fit het beste algoritme overall is. Na First Fit Decreasing was Best Fit het meest effici\"ent qua bingebruik en na Next Fit was Best Fit het ook het snelste algoritme. First Fit Decreasing heeft een vrij hoge doorloptijd en Next Fit heeft vrij ineffici\"ent bingebruik in vergelijking met de andere algorithmes. Hierdoor is Best Fit naar aanleiding van onze resultaten het beste algoritme voor het bin-packing probleem.
% chapter conclusie(end)

\end{document}